{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Sum of Prefix Scores of Strings"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #trie #array #string #counting"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #字典树 #数组 #字符串 #计数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: sumPrefixScores"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #字符串的前缀分数和"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个长度为 <code>n</code> 的数组 <code>words</code> ，该数组由 <strong>非空</strong> 字符串组成。</p>\n",
    "\n",
    "<p>定义字符串 <code>word</code> 的 <strong>分数</strong> 等于以 <code>word</code> 作为 <strong>前缀</strong> 的 <code>words[i]</code> 的数目。</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>例如，如果 <code>words = [\"a\", \"ab\", \"abc\", \"cab\"]</code> ，那么 <code>\"ab\"</code> 的分数是 <code>2</code> ，因为 <code>\"ab\"</code> 是 <code>\"ab\"</code> 和 <code>\"abc\"</code> 的一个前缀。</li>\n",
    "</ul>\n",
    "\n",
    "<p>返回一个长度为<em> </em><code>n</code> 的数组<em> </em><code>answer</code><em> </em>，其中<em> </em><code>answer[i]</code><em> </em>是<em>&nbsp;</em><code>words[i]</code> 的每个非空前缀的分数 <strong>总和</strong> <em>。</em></p>\n",
    "\n",
    "<p><strong>注意：</strong>字符串视作它自身的一个前缀。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>words = [\"abc\",\"ab\",\"bc\",\"b\"]\n",
    "<strong>输出：</strong>[5,4,3,2]\n",
    "<strong>解释：</strong>对应每个字符串的答案如下：\n",
    "- \"abc\" 有 3 个前缀：\"a\"、\"ab\" 和 \"abc\" 。\n",
    "- 2 个字符串的前缀为 \"a\" ，2 个字符串的前缀为 \"ab\" ，1 个字符串的前缀为 \"abc\" 。\n",
    "总计 answer[0] = 2 + 2 + 1 = 5 。\n",
    "- \"ab\" 有 2 个前缀：\"a\" 和 \"ab\" 。\n",
    "- 2 个字符串的前缀为 \"a\" ，2 个字符串的前缀为 \"ab\" 。\n",
    "总计 answer[1] = 2 + 2 = 4 。\n",
    "- \"bc\" 有 2 个前缀：\"b\" 和 \"bc\" 。\n",
    "- 2 个字符串的前缀为 \"b\" ，1 个字符串的前缀为 \"bc\" 。 \n",
    "总计 answer[2] = 2 + 1 = 3 。\n",
    "- \"b\" 有 1 个前缀：\"b\"。\n",
    "- 2 个字符串的前缀为 \"b\" 。\n",
    "总计 answer[3] = 2 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>words = [\"abcd\"]\n",
    "<strong>输出：</strong>[4]\n",
    "<strong>解释：</strong>\n",
    "\"abcd\" 有 4 个前缀 \"a\"、\"ab\"、\"abc\" 和 \"abcd\"。\n",
    "每个前缀的分数都是 1 ，总计 answer[0] = 1 + 1 + 1 + 1 = 4 。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= words.length &lt;= 1000</code></li>\n",
    "\t<li><code>1 &lt;= words[i].length &lt;= 1000</code></li>\n",
    "\t<li><code>words[i]</code> 由小写英文字母组成</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [sum-of-prefix-scores-of-strings](https://leetcode.cn/problems/sum-of-prefix-scores-of-strings/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [sum-of-prefix-scores-of-strings](https://leetcode.cn/problems/sum-of-prefix-scores-of-strings/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[\"abc\",\"ab\",\"bc\",\"b\"]', '[\"abcd\"]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Tree:\n",
    "    def __init__(self):\n",
    "        self.root = dict()\n",
    "\n",
    "    def update(self, word: str):\n",
    "        parent = self.root\n",
    "\n",
    "        for ch in word:\n",
    "            child = parent.get(ch, None)\n",
    "\n",
    "            if child is None:\n",
    "                child = dict()\n",
    "                parent[ch] = child\n",
    "\n",
    "            child[None] = child.get(None, 0) + 1\n",
    "            parent = child\n",
    "\n",
    "    def count(self, word: str) -> int:\n",
    "        parent = self.root\n",
    "        ans: int = 0\n",
    "\n",
    "        for ch in word:\n",
    "            child = parent[ch]\n",
    "            ans += child[None]\n",
    "\n",
    "            parent = child\n",
    "\n",
    "        return ans\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def sumPrefixScores(self, words: list[str]) -> list[int]:\n",
    "        tree = Tree()\n",
    "\n",
    "        for word in words:\n",
    "            tree.update(word)\n",
    "\n",
    "        return [tree.count(word) for word in words]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumPrefixScores(self, words: List[str]) -> List[int]:\n",
    "        d = dict()\n",
    "        for word in words:\n",
    "            cur = d\n",
    "            for w in word:\n",
    "                if w not in cur:\n",
    "                    cur[w] = {}\n",
    "                    cur[w]['cnt'] = 0\n",
    "                cur = cur[w]\n",
    "                cur['cnt'] += 1\n",
    "        #print(d)\n",
    "        n = len(words)\n",
    "        ans = [0] * n\n",
    "        for i,word in enumerate(words):\n",
    "            cur = d\n",
    "            for w in word:\n",
    "                cur = cur[w]\n",
    "                ans[i] += cur['cnt']\n",
    "        return ans\n",
    "\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumPrefixScores(self, words: List[str]) -> List[int]:\n",
    "        my_dict={}\n",
    "        for word in words:\n",
    "            temp=my_dict\n",
    "            for letter in word:\n",
    "                if letter in temp:\n",
    "                    temp[letter]['flag']+=1\n",
    "                    temp=temp[letter]\n",
    "                else:\n",
    "                    temp[letter]={}\n",
    "                    temp[letter]['flag']=1\n",
    "                    temp=temp[letter]\n",
    "        \n",
    "        result_mat=[]\n",
    "\n",
    "        for word in words:\n",
    "            result=0\n",
    "            temp=my_dict\n",
    "            for letter in word:\n",
    "                result=result+temp[letter]['flag']\n",
    "                temp=temp[letter]\n",
    "            result_mat.append(result)\n",
    "\n",
    "        return result_mat\n",
    "\n",
    "        \n",
    "\n",
    "\n",
    "                \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def max_(a, b):\n",
    "    return a if a > b else b\n",
    "\n",
    "\n",
    "def min_(a, b):\n",
    "    return a if a < b else b\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def sumPrefixScores(self, words: List[str]) -> List[int]:\n",
    "        dct = dict()\n",
    "        for word in words:\n",
    "            cur = dct\n",
    "            for w in word:\n",
    "                if w not in cur:\n",
    "                    cur[w] = dict()\n",
    "                cur = cur[w]\n",
    "                cur[\"cnt\"] = cur.get(\"cnt\", 0) + 1\n",
    "        \n",
    "        def dfs(cur_dct, i):\n",
    "            nonlocal cnt\n",
    "            if i == n:\n",
    "                return \n",
    "            if word[i] in cur_dct:\n",
    "                nex = cur_dct[word[i]]\n",
    "                cnt += nex[\"cnt\"]\n",
    "                dfs(nex, i+1)\n",
    "            return \n",
    "        \n",
    "        ans = []\n",
    "        for word in words:\n",
    "            n = len(word)\n",
    "            cnt = 0\n",
    "            dfs(dct, 0)\n",
    "            ans.append(cnt)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumPrefixScores(self, words: List[str]) -> List[int]:\n",
    "        tree = lambda: defaultdict(tree)\n",
    "        root = tree()\n",
    "        for word in words:\n",
    "            cur = root\n",
    "            for c in word:\n",
    "                cur = cur[c]\n",
    "                cur[None] = cur.get(None, 0) + 1\n",
    "        ans = []\n",
    "        for word in words:\n",
    "            cur, sum = root, 0\n",
    "            for c in word:\n",
    "                cur = cur[c]\n",
    "                sum += cur[None]\n",
    "            ans.append(sum)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumPrefixScores(self, words: List[str]) -> List[int]:\n",
    "        trie = lambda: defaultdict(trie)\n",
    "        root = trie()\n",
    "        for word in words:\n",
    "            cur = root\n",
    "            for c in word:\n",
    "                cur = cur[c]\n",
    "                cur[None] = cur.get(None, 0) + 1  # 更新所有前缀的分数\n",
    "\n",
    "        ans = []\n",
    "        for word in words:\n",
    "            cur, sum = root, 0\n",
    "            for c in word:\n",
    "                cur = cur[c]\n",
    "                sum += cur[None]  # 累加分数，即可得到答案\n",
    "            ans.append(sum)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumPrefixScores(self, words: List[str]) -> List[int]:\n",
    "        trie = lambda : defaultdict(trie)\n",
    "        root = trie()\n",
    "        for word in words:\n",
    "            cur = root\n",
    "            for c in word:\n",
    "                cur = cur[c]\n",
    "                cur[None] = cur.get(None, 0) + 1\n",
    "        \n",
    "        ans = []\n",
    "        for word in words:\n",
    "            cur, sum = root, 0\n",
    "            for c in word:\n",
    "                cur = cur[c]\n",
    "                sum += cur[None]\n",
    "            ans.append(sum)\n",
    "        return ans\n",
    "        # cnt = Counter()\n",
    "        # ans = [0] * len(words)\n",
    "        # for word in words:\n",
    "        #     for i in range(1, len(word)+1):\n",
    "        #         cnt[word[:i]] += 1\n",
    "\n",
    "        # for i,word in enumerate(words):\n",
    "        #     for j in range(1, len(word) + 1):\n",
    "        #         ans[i] += cnt[word[:j]]\n",
    "        # return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumPrefixScores(self, words: List[str]) -> List[int]:\n",
    "        trie = lambda: defaultdict(trie)\n",
    "        root = trie()\n",
    "        for word in words:\n",
    "            cur = root\n",
    "            for c in word:\n",
    "                cur = cur[c]\n",
    "                cur[None] = cur.get(None, 0) + 1  # 更新所有前缀的分数\n",
    "\n",
    "        ans = []\n",
    "        for word in words:\n",
    "            cur, sum = root, 0\n",
    "            for c in word:\n",
    "                cur = cur[c]\n",
    "                sum += cur[None]  # 累加分数，即可得到答案\n",
    "            ans.append(sum)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumPrefixScores(self, words: List[str]) -> List[int]:\n",
    "        trie = lambda: defaultdict(trie)\n",
    "        root = trie()\n",
    "        for word in words:\n",
    "            cur = root\n",
    "            for c in word:\n",
    "                cur = cur[c]\n",
    "                cur[None] = cur.get(None, 0) + 1  # 更新所有前缀的分数\n",
    "\n",
    "        ans = []\n",
    "        for word in words:\n",
    "            cur, sum = root, 0\n",
    "            for c in word:\n",
    "                cur = cur[c]\n",
    "                sum += cur[None]  # 累加分数，即可得到答案\n",
    "            ans.append(sum)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumPrefixScores(self, words: List[str]) -> List[int]:\n",
    "        trie = lambda: defaultdict(trie)\n",
    "        root = trie()\n",
    "        for word in words:\n",
    "            cur = root\n",
    "            for c in word:\n",
    "                cur = cur[c]\n",
    "                cur[None] = cur.get(None, 0) + 1  # 更新所有前缀的分数\n",
    "\n",
    "        ans = []\n",
    "        for word in words:\n",
    "            cur, sum = root, 0\n",
    "            for c in word:\n",
    "                cur = cur[c]\n",
    "                sum += cur[None]  # 累加分数，即可得到答案\n",
    "            ans.append(sum)\n",
    "        return ans\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumPrefixScores(self, words: List[str]) -> List[int]:\n",
    "        trie = lambda: defaultdict(trie)\n",
    "        root = trie()\n",
    "        for word in words:\n",
    "            cur = root\n",
    "            for c in word:\n",
    "                cur = cur[c]\n",
    "                cur[None] = cur.get(None, 0) + 1  # 更新所有前缀的分数\n",
    "\n",
    "        ans = []\n",
    "        for word in words:\n",
    "            cur, sum = root, 0\n",
    "            for c in word:\n",
    "                cur = cur[c]\n",
    "                sum += cur[None]  # 累加分数，即可得到答案\n",
    "            ans.append(sum)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumPrefixScores(self, words: List[str]) -> List[int]:\n",
    "        trie = lambda: defaultdict(trie)\n",
    "        root = trie()\n",
    "        for word in words:\n",
    "            cur = root\n",
    "            for c in word:\n",
    "                cur = cur[c]\n",
    "                cur[None] = cur.get(None, 0) + 1  # 更新所有前缀的分数\n",
    "\n",
    "        ans = []\n",
    "        for word in words:\n",
    "            cur, sum = root, 0\n",
    "            for c in word:\n",
    "                cur = cur[c]\n",
    "                sum += cur[None]  # 累加分数，即可得到答案\n",
    "            ans.append(sum)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumPrefixScores(self, words: List[str]) -> List[int]:\n",
    "        trie = lambda: defaultdict(trie)\n",
    "        root = trie()\n",
    "        for word in words:\n",
    "            cur = root\n",
    "            for c in word:\n",
    "                cur = cur[c]\n",
    "                cur['ps'] = cur.get('ps', 0) + 1\n",
    "\n",
    "        res = []\n",
    "        for word in words:\n",
    "            cur, partres = root, 0\n",
    "            for c in word:\n",
    "                cur = cur[c]\n",
    "                partres += cur['ps']\n",
    "\n",
    "            res.append(partres)\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumPrefixScores(self, words: List[str]) -> List[int]:\n",
    "        trie=lambda:defaultdict(trie)\n",
    "        root=trie()\n",
    "        for word in words:\n",
    "            cur=root\n",
    "            for c in word:\n",
    "                cur=cur[c]\n",
    "                cur[None]=cur.get(None,0)+1\n",
    "\n",
    "        ans=[]\n",
    "        for word in words:\n",
    "            cur,total=root,0\n",
    "            for c in word:\n",
    "                cur=cur[c]\n",
    "                total+=cur[None]\n",
    "            ans.append(total)\n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumPrefixScores(self, words: List[str]) -> List[int]:\n",
    "        trie = lambda: defaultdict(trie)\n",
    "        root = trie()\n",
    "        for word in words:\n",
    "            cur = root\n",
    "            for c in word:\n",
    "                cur = cur[c]\n",
    "                cur[None] = cur.get(None, 0) + 1  # 更新所有前缀的分数\n",
    "\n",
    "        ans = []\n",
    "        for word in words:\n",
    "            cur, sum = root, 0\n",
    "            for c in word:\n",
    "                cur = cur[c]\n",
    "                sum += cur[None]  # 累加分数，即可得到答案\n",
    "            ans.append(sum)\n",
    "        return ans\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumPrefixScores(self, words: List[str]) -> List[int]:\n",
    "        trie = lambda: defaultdict(trie)\n",
    "        root = trie()\n",
    "        for word in words:\n",
    "            cur = root\n",
    "            for c in word:\n",
    "                cur = cur[c]\n",
    "                cur[None] = cur.get(None, 0) + 1  # 更新所有前缀的分数\n",
    "\n",
    "        ans = []\n",
    "        for word in words:\n",
    "            cur, sum = root, 0\n",
    "            for c in word:\n",
    "                cur = cur[c]\n",
    "                sum += cur[None]  # 累加分数，即可得到答案\n",
    "            ans.append(sum)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumPrefixScores(self, words: List[str]) -> List[int]:\n",
    "        trie = lambda: defaultdict(trie)\n",
    "        root = trie()\n",
    "        for word in words:\n",
    "            cur = root\n",
    "            for c in word:\n",
    "                cur = cur[c]\n",
    "                cur[None] = cur.get(None, 0) + 1  # 更新所有前缀的分数\n",
    "\n",
    "        ans = []\n",
    "        for word in words:\n",
    "            cur, sum = root, 0\n",
    "            for c in word:\n",
    "                cur = cur[c]\n",
    "                sum += cur[None]  # 累加分数，即可得到答案\n",
    "            ans.append(sum)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumPrefixScores(self, words: List[str]) -> List[int]:\n",
    "        # trie 前缀树\n",
    "        trie = lambda: defaultdict(trie)\n",
    "        root = trie()\n",
    "        for word in words:\n",
    "            cur = root\n",
    "            for c in word:\n",
    "                cur  = cur[c]\n",
    "                cur[None] = cur.get(None, 0) + 1\n",
    "\n",
    "        ans = []\n",
    "        for word in words:\n",
    "            cur, sum = root, 0\n",
    "            for c in word:\n",
    "                cur = cur[c]\n",
    "                sum += cur[None]\n",
    "            ans.append(sum)\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumPrefixScores(self, words: List[str]) -> List[int]:\n",
    "        trie = lambda: defaultdict(trie)\n",
    "        root = trie()\n",
    "        for word in words:\n",
    "            cur = root\n",
    "            for c in word:\n",
    "                cur = cur[c]\n",
    "                cur[\"0\"] = cur.get(\"0\", 0) + 1\n",
    "        \n",
    "        ans = []\n",
    "        for word in words:\n",
    "            s = 0\n",
    "            cur = root\n",
    "            for c in word:\n",
    "                cur = cur[c]\n",
    "                s += cur.get(\"0\", 0)\n",
    "            ans.append(s)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumPrefixScores(self, words: List[str]) -> List[int]:\n",
    "        mkfunc = lambda: defaultdict(mkfunc)\n",
    "        trie = mkfunc()\n",
    "        for word in words:\n",
    "            node = trie\n",
    "            for c in word:\n",
    "                node = node[c]\n",
    "                if None not in node:\n",
    "                    node[None] = 1\n",
    "                else:\n",
    "                    node[None] += 1\n",
    "        answer = [0]*len(words)\n",
    "        for i, word in enumerate(words):\n",
    "            node = trie\n",
    "            score = 0\n",
    "            for c in word:\n",
    "                node = node[c]\n",
    "                score += node[None]\n",
    "            answer[i] = score\n",
    "        return answer\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Trie:\n",
    "    class Node:\n",
    "        __slots__ = 'children', 'numOfPrefix'\n",
    "        def __init__(self):\n",
    "            self.children = defaultdict(Trie.Node)\n",
    "            self.numOfPrefix = 0\n",
    "\n",
    "    def __init__(self):\n",
    "        self.root = self.Node()\n",
    "    \n",
    "    def insert(self, word):\n",
    "        cur = self.root\n",
    "        for ch in word:\n",
    "            cur = cur.children[ch]\n",
    "            cur.numOfPrefix += 1\n",
    "\n",
    "class Solution:\n",
    "    def sumPrefixScores(self, words: List[str]) -> List[int]:\n",
    "        n = len(words)\n",
    "        trie = Trie()\n",
    "\n",
    "        for word in words:\n",
    "            trie.insert(word)\n",
    "\n",
    "        ans = [0]*n\n",
    "        for i, word in enumerate(words):\n",
    "            cur = trie.root\n",
    "            for ch in word:\n",
    "                cur = cur.children[ch]\n",
    "                ans[i] += cur.numOfPrefix\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumPrefixScores(self, words: List[str]) -> List[int]:\n",
    "\n",
    "    # 对字典树 里面的元素变成dict， key ： 【value：count】 count记录的是个数\n",
    "    #     边遍历，边加\n",
    "        res = []\n",
    "        start = {}\n",
    "        for word in words:\n",
    "            temp = start\n",
    "            for c in word:\n",
    "                if c not in temp:\n",
    "                    new = {}\n",
    "                    temp[c] = [new,0]\n",
    "                temp[c][1] += 1\n",
    "                # res += temp[c][1]\n",
    "                temp = temp[c][0]\n",
    "        # return res\n",
    "        for word in words:\n",
    "            temp = start\n",
    "            count = 0\n",
    "            for c in word:\n",
    "                count += temp[c][1]\n",
    "                temp = temp[c][0]\n",
    "            res.append(count)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Trie:\n",
    "    __slots__ = ['children', 'isEnd', 'cnt']\n",
    "    def __init__(self):\n",
    "        self.children = [None] * 26\n",
    "        self.isEnd = False\n",
    "        self.cnt = 0\n",
    "\n",
    "    def searchPrefix(self, prefix: str) -> \"Trie\":\n",
    "        '''\n",
    "        搜索前缀\n",
    "        '''\n",
    "        node = self\n",
    "        for ch in prefix:\n",
    "            idx = ord(ch) - ord(\"a\")\n",
    "            if not node.children[idx]:\n",
    "                return None\n",
    "            node = node.children[idx]\n",
    "        return node\n",
    "\n",
    "    def insert(self, word: str) -> None:\n",
    "        '''\n",
    "        插入一个单词\n",
    "        '''\n",
    "        node = self\n",
    "        for ch in word:\n",
    "            idx = ord(ch) - ord(\"a\")\n",
    "            if not node.children[idx]:\n",
    "                node.children[idx] = Trie()\n",
    "            node = node.children[idx]\n",
    "            node.cnt += 1\n",
    "        node.isEnd = True\n",
    "\n",
    "    def cal(self, word):\n",
    "        res = 0\n",
    "        node = self\n",
    "        for ch in word:\n",
    "            idx = ord(ch) - ord(\"a\")\n",
    "            if not node.children[idx]:\n",
    "                node.children[idx] = Trie()\n",
    "            node = node.children[idx]\n",
    "            res += node.cnt\n",
    "        return res\n",
    "        \n",
    "\n",
    "    def search(self, word: str) -> bool:\n",
    "        '''\n",
    "        搜索 word 是否存在\n",
    "        '''\n",
    "        node = self.searchPrefix(word)\n",
    "        return node is not None and node.isEnd\n",
    "\n",
    "    def startsWith(self, prefix: str) -> bool:\n",
    "        '''\n",
    "        搜索是否存在前缀\n",
    "        '''\n",
    "        return self.searchPrefix(prefix) is not None\n",
    "\n",
    "class Solution:\n",
    "    def sumPrefixScores(self, words: List[str]) -> List[int]:\n",
    "        t = Trie()\n",
    "        for w in words:\n",
    "            t.insert(w)\n",
    "\n",
    "        return [t.cal(w) for w in words]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumPrefixScores(self, words: List[str]) -> List[int]:\n",
    "        dct = defaultdict()\n",
    "        ans = [0] * len(words)\n",
    "        for  word in words:\n",
    "            d = dct\n",
    "            for w in word:\n",
    "                if w not in d:\n",
    "                    d[w] = [defaultdict(), 0]\n",
    "                d[w][1] += 1\n",
    "                d = d[w][0]\n",
    "    \n",
    "        for i, word in enumerate(words):\n",
    "            d = dct\n",
    "            for w in word:\n",
    "                #if w not in d:\n",
    "                    #break\n",
    "                ans[i] += d[w][1]\n",
    "                d = d[w][0]   \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumPrefixScores(self, words: List[str]) -> List[int]:\n",
    "        N = 1024\n",
    "        son = [[0] * 26 for _ in range(N)]\n",
    "        cnt = [0] * N\n",
    "        idx = 0\n",
    "        def insert(s: str):\n",
    "            p = 0\n",
    "            for i in s:\n",
    "                u = ord(i) - ord('a')\n",
    "                if not son[p][u]:\n",
    "                    nonlocal idx, N\n",
    "                    idx += 1\n",
    "                    son[p][u] = idx\n",
    "                p = son[p][u]\n",
    "                if p == N:\n",
    "                    son.extend([[0] * 26 for _ in range(N)])\n",
    "                    cnt.extend([0] * N)\n",
    "                    N *= 2\n",
    "                cnt[p] += 1\n",
    "        def query(s: str) -> int:\n",
    "            p, ret = 0, 0\n",
    "            for i in s:\n",
    "                u = ord(i) - ord('a')\n",
    "                p = son[p][u]\n",
    "                ret += cnt[p]\n",
    "            return ret\n",
    "        for s in words:\n",
    "            insert(s)\n",
    "        return [query(s) for s in words]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumPrefixScores(self, words: List[str]) -> List[int]:\n",
    "        N = 1024\n",
    "        son = [[0] * 26 for _ in range(N)]\n",
    "        cnt = [0] * N\n",
    "        idx = 0\n",
    "        def insert(s: str):\n",
    "            p = 0\n",
    "            for i in s:\n",
    "                u = ord(i) - ord('a')\n",
    "                if not son[p][u]:\n",
    "                    nonlocal idx, N\n",
    "                    idx += 1\n",
    "                    son[p][u] = idx\n",
    "                p = son[p][u]\n",
    "                if p == N:\n",
    "                    son.extend([[0] * 26 for _ in range(N)])\n",
    "                    cnt.extend([0] * N)\n",
    "                    N *= 2\n",
    "                cnt[p] += 1\n",
    "        def query(s: str) -> int:\n",
    "            p, ret = 0, 0\n",
    "            for i in s:\n",
    "                u = ord(i) - ord('a')\n",
    "                p = son[p][u]\n",
    "                ret += cnt[p]\n",
    "            return ret\n",
    "        for s in words:\n",
    "            insert(s)\n",
    "        return [query(s) for s in words]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Node:\n",
    "    __slots__ = \"son\", \"score\", \"ids\"\n",
    "\n",
    "    def __init__(self):\n",
    "        self.son = defaultdict(Node)\n",
    "        self.score = 0\n",
    "        self.ids = []\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def sumPrefixScores(self, words: List[str]) -> List[int]:\n",
    "        root = Node()\n",
    "        for i, word in enumerate(words):\n",
    "            cur = root\n",
    "            for c in word:\n",
    "                cur = cur.son[c]\n",
    "                cur.score += 1\n",
    "            cur.ids.append(i)\n",
    "\n",
    "        ans = [0] * len(words)\n",
    "\n",
    "        def dfs(node, sum):\n",
    "            if node is None:\n",
    "                return\n",
    "            sum += node.score\n",
    "            for i in node.ids:\n",
    "                ans[i] = sum\n",
    "            for c in node.son.values():\n",
    "                dfs(c, sum)\n",
    "\n",
    "        dfs(root, 0)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Node:\n",
    "    __slots__ = 'son', 'ids', 'score'\n",
    "\n",
    "    def __init__(self):\n",
    "        self.son = defaultdict(Node)\n",
    "        self.ids = []\n",
    "        self.score = 0\n",
    "\n",
    "class Solution:\n",
    "    def sumPrefixScores(self, words: List[str]) -> List[int]:\n",
    "        root = Node()\n",
    "        for i, word in enumerate(words):\n",
    "            cur = root\n",
    "            for c in word:\n",
    "                cur = cur.son[c]\n",
    "                cur.score += 1  # 更新所有前缀的分数\n",
    "            cur.ids.append(i)\n",
    "\n",
    "        ans = [0] * len(words)\n",
    "        def dfs(node: Node, sum: int) -> None:\n",
    "            sum += node.score  # 累加分数，即可得到答案\n",
    "            for i in node.ids:\n",
    "                ans[i] = sum\n",
    "            for child in node.son.values():\n",
    "                if child:\n",
    "                    dfs(child, sum)\n",
    "        dfs(root, 0)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Node:\n",
    "    __slots__ = \"son\", \"score\", \"ids\"\n",
    "\n",
    "    def __init__(self):\n",
    "        self.son = defaultdict(Node)\n",
    "        self.score = 0\n",
    "        self.ids = []\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def sumPrefixScores(self, words: List[str]) -> List[int]:\n",
    "        root = Node()\n",
    "        for i, word in enumerate(words):\n",
    "            cur = root\n",
    "            for c in word:\n",
    "                cur = cur.son[c]\n",
    "                cur.score += 1\n",
    "            cur.ids.append(i)\n",
    "\n",
    "        ans = [0] * len(words)\n",
    "\n",
    "        def dfs(node, sum):\n",
    "            if node is None:\n",
    "                return\n",
    "            sum += node.score\n",
    "            for i in node.ids:\n",
    "                ans[i] = sum\n",
    "            for c in node.son.values():\n",
    "                dfs(c, sum)\n",
    "\n",
    "        dfs(root, 0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Node:\n",
    "    __slots__ = 'son','score','ids'\n",
    "    def __init__(self):\n",
    "        self.son = defaultdict(Node) # 表示的是cur下的二十六个字母的字典\n",
    "        self.score = 0\n",
    "        self.ids = []\n",
    "class Solution:\n",
    "    def sumPrefixScores(self, words: List[str]) -> List[int]:\n",
    "        # 核心思想，找出每个word的所有前缀，统计每个前缀的单词个数，然后加在一起\n",
    "        # 字典树（一种存储字符串的数据结构）\n",
    "        # 第一步，存储\n",
    "        root = Node()\n",
    "        for i,word in enumerate(words):\n",
    "            cur = root\n",
    "            for c in word:\n",
    "            # 正常应该是判断有没有cur.son[c]没有的话就创建cur.son[c]\n",
    "                cur = cur.son[c]\n",
    "                cur.score += 1\n",
    "            cur.ids.append(i)\n",
    "        # 第二步，找每个单词的分数\n",
    "        # 类似于遍历二叉树\n",
    "        ans = [0]*len(words)\n",
    "        def dfs(node,sum_):\n",
    "            if node is None:return\n",
    "            sum_ += node.score\n",
    "            for i in node.ids:\n",
    "                ans[i] = sum_\n",
    "            # 遍历它的儿子\n",
    "            for child in node.son.values():\n",
    "                dfs(child,sum_)\n",
    "        dfs(root,0)\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumPrefixScores(self, words: List[str]) -> List[int]:\n",
    "        class Node:\n",
    "            def __init__(self):\n",
    "                self.cnt = 1\n",
    "                self.son = dict()\n",
    "            \n",
    "        class Trie:\n",
    "            def __init__(self):\n",
    "                self.root = Node()\n",
    "                \n",
    "            def insert(self, s):\n",
    "        \n",
    "                now = self.root\n",
    "                for x in s:\n",
    "                    if x not in now.son:\n",
    "                        now.son[x] = Node()\n",
    "                    else:\n",
    "                        now.son[x].cnt += 1\n",
    "                    now = now.son[x]\n",
    "            def query(self, s):\n",
    "                now = self.root\n",
    "                ret = 0\n",
    "                for x in s:\n",
    "                    son = now.son[x]\n",
    "                    ret += son.cnt\n",
    "                    now = son\n",
    "                return ret\n",
    "        trie = Trie()\n",
    "        for w in words:\n",
    "            trie.insert(w)\n",
    "        return [trie.query(w) for w in words]\n",
    "                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Trie:\n",
    "    def __init__(self):\n",
    "        self.children=dict()\n",
    "        self.s=0\n",
    "\n",
    "class Solution:\n",
    "    def sumPrefixScores(self, words: List[str]) -> List[int]:\n",
    "        root=Trie()\n",
    "        for word in words:\n",
    "            node=root\n",
    "            for c in word:\n",
    "                if c not in node.children:\n",
    "                    node.children[c]=Trie()\n",
    "                node=node.children[c]\n",
    "                node.s+=1\n",
    "        ans=[]\n",
    "        for word in words:\n",
    "            node=root\n",
    "            temp=0\n",
    "            for c in word:\n",
    "                node=node.children[c]\n",
    "                temp+=node.s\n",
    "            ans.append(temp)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Node:\n",
    "    def __init__ (self, letter):\n",
    "        self.occurance = 1\n",
    "        self.letter = letter\n",
    "        self.children = {}\n",
    "class Solution:\n",
    "    def sumPrefixScores(self, words: List[str]) -> List[int]:\n",
    "        roots = {}\n",
    "        for word in words:\n",
    "            rootLetter = word[0]\n",
    "            if rootLetter in roots:\n",
    "                root = roots[rootLetter]\n",
    "                root.occurance +=1\n",
    "            else:\n",
    "                root = Node(rootLetter)\n",
    "                roots[rootLetter] = root\n",
    "            for letter in word[1:]:\n",
    "                if letter in root.children:\n",
    "                    root = root.children[letter]\n",
    "                    root.occurance +=1\n",
    "                else:\n",
    "                    root.children[letter] = Node(letter)\n",
    "                    root = root.children[letter]\n",
    "        n = len(words)\n",
    "        ans = [0] * n\n",
    "        for i in range(n):\n",
    "            word = words[i]\n",
    "            value = 0\n",
    "            currentRoots = roots\n",
    "            for letter in word:\n",
    "                value += currentRoots[letter].occurance\n",
    "                currentRoots = currentRoots[letter].children\n",
    "            ans[i] = value\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Treenode:\n",
    "    def __init__(self):\n",
    "        self.is_end=False\n",
    "        self.children={}\n",
    "        self.val=0\n",
    "\n",
    "class Trie:\n",
    "\n",
    "    def __init__(self):\n",
    "        self.root=Treenode()\n",
    "\n",
    "    def insert(self, word: str) -> None:\n",
    "        node=self.root\n",
    "        for c in word:\n",
    "            if c not in node.children:\n",
    "                node.children[c]=Treenode()\n",
    "            \n",
    "            node=node.children[c]\n",
    "            node.val+=1\n",
    "            \n",
    "        node.is_end=True\n",
    "\n",
    "    def search(self, word: str) -> bool:\n",
    "        node=self.root\n",
    "        for c in word:\n",
    "            if c not in node.children:\n",
    "                return False\n",
    "            node=node.children[c]\n",
    "        return node.is_end\n",
    "\n",
    "\n",
    "    def startsWith(self, word: str) -> bool:\n",
    "        node=self.root\n",
    "        for c in word:\n",
    "            if c not in node.children:\n",
    "                return False\n",
    "            node=node.children[c]\n",
    "        return True\n",
    "\n",
    "    def findnum(self,word: str) -> int:\n",
    "        node=self.root\n",
    "        ans=0\n",
    "        for c in word:\n",
    "            if c not in node.children:\n",
    "                return ans\n",
    "            \n",
    "            node=node.children[c]\n",
    "            ans=ans+node.val\n",
    "        return ans\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def sumPrefixScores(self, words: List[str]) -> List[int]:\n",
    "        y=Trie()\n",
    "        for w in words:\n",
    "            y.insert(w)\n",
    "        ans=[]\n",
    "        y.root.val=0\n",
    "        for w in words:\n",
    "            ans.append(y.findnum(w))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Trie:\n",
    "    def __init__(self):\n",
    "        self.children=defaultdict()\n",
    "        self.s=0\n",
    "\n",
    "class Solution:\n",
    "    def sumPrefixScores(self, words: List[str]) -> List[int]:\n",
    "        root=Trie()\n",
    "        for word in words:\n",
    "            node=root\n",
    "            for c in word:\n",
    "                if c not in node.children:\n",
    "                    node.children[c]=Trie()\n",
    "                node=node.children[c]\n",
    "                node.s+=1\n",
    "        ans=[]\n",
    "        for word in words:\n",
    "            node=root\n",
    "            temp=0\n",
    "            for c in word:\n",
    "                node=node.children[c]\n",
    "                temp+=node.s\n",
    "            ans.append(temp)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Trie:\n",
    "    def __init__(self):\n",
    "        self.children=defaultdict(Trie)\n",
    "        self.s=0\n",
    "\n",
    "class Solution:\n",
    "    def sumPrefixScores(self, words: List[str]) -> List[int]:\n",
    "        root=Trie()\n",
    "        for word in words:\n",
    "            node=root\n",
    "            for c in word:\n",
    "                if c not in node.children:\n",
    "                    node.children[c]=Trie()\n",
    "                node=node.children[c]\n",
    "                node.s+=1\n",
    "        ans=[]\n",
    "        for word in words:\n",
    "            node=root\n",
    "            temp=0\n",
    "            for c in word:\n",
    "                node=node.children[c]\n",
    "                temp+=node.s\n",
    "            ans.append(temp)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class TrieNode:\n",
    "    def __init__(self, end=False, sumnum=0):\n",
    "        self.end = end\n",
    "        self.sumnum = sumnum\n",
    "        self.children = defaultdict(TrieNode)\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def sumPrefixScores(self, words: List[str]) -> List[int]:\n",
    "        trie = TrieNode()\n",
    "        res = [0] * len(words)\n",
    "        for i, word in enumerate(words):\n",
    "            dummy = trie\n",
    "            for c in word:\n",
    "                dummy = dummy.children[ord(c) - ord('a')]\n",
    "                dummy.sumnum += 1\n",
    "            dummy.end = True\n",
    "        for i, word in enumerate(words):\n",
    "            dummy = trie\n",
    "            for c in word:\n",
    "                dummy = dummy.children[ord(c) - ord('a')]\n",
    "                res[i] += dummy.sumnum\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Node:\n",
    "    __slot__ = \"son\", \"score\"\n",
    "\n",
    "    def __init__(self):\n",
    "        self.son = defaultdict(Node)\n",
    "        self.score = 0\n",
    "\n",
    "class Solution:\n",
    "    def sumPrefixScores(self, words: List[str]) -> List[int]:\n",
    "\n",
    "        root = Node()\n",
    "        for i, word in enumerate(words):\n",
    "            cur = root\n",
    "            for c in word:\n",
    "                cur = cur.son[c]\n",
    "                cur.score += 1\n",
    "        \n",
    "        ans = [0] * len(words)\n",
    "\n",
    "        for i, word in enumerate(words):\n",
    "            cur = root\n",
    "            for c in word:\n",
    "                ans[i] += cur.son[c].score\n",
    "                cur = cur.son[c]\n",
    "\n",
    "        return ans \n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Trie:\n",
    "    def __init__(self):\n",
    "        self.child = [None]*26\n",
    "        self.count = 0\n",
    "    \n",
    "    def insert(self, words)->None:\n",
    "        node = self\n",
    "        for i in range(len(words)):\n",
    "            tmp = ord(words[i]) - ord('a')\n",
    "            if not node.child[tmp]:\n",
    "                node.child[tmp] = Trie()\n",
    "            node = node.child[tmp]\n",
    "            node.count += 1\n",
    "\n",
    "\n",
    "    def getNums(self,words)->int:\n",
    "        node = self\n",
    "        nums = 0\n",
    "        for i in range(len(words)):\n",
    "            tmp = ord(words[i]) - ord('a')\n",
    "            if node.child[tmp]:\n",
    "                nums+=node.child[tmp].count\n",
    "            else:\n",
    "                break\n",
    "            node = node.child[tmp]\n",
    "        return nums\n",
    "\n",
    "class Solution:\n",
    "    def sumPrefixScores(self, words: List[str]) -> List[int]:\n",
    "        #构建前缀树\n",
    "        trie = Trie()\n",
    "        answer = []\n",
    "        for i in range(len(words)):\n",
    "            trie.insert(words[i])\n",
    "            \n",
    "        for i in range(len(words)):\n",
    "            answer.append(trie.getNums(words[i]))\n",
    "        return answer\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Trie:\n",
    "    def __init__(self):\n",
    "        self.child = [None]*26\n",
    "        self.count = 0\n",
    "    \n",
    "    def insert(self, words)->None:\n",
    "        node = self\n",
    "        for i in range(len(words)):\n",
    "            tmp = ord(words[i]) - ord('a')\n",
    "            if not node.child[tmp]:\n",
    "                node.child[tmp] = Trie()\n",
    "            node = node.child[tmp]\n",
    "            node.count += 1\n",
    "\n",
    "\n",
    "    def getNums(self,words)->int:\n",
    "        node = self\n",
    "        nums = 0\n",
    "        for i in range(len(words)):\n",
    "            tmp = ord(words[i]) - ord('a')\n",
    "            if node.child[tmp]:\n",
    "                nums+=node.child[tmp].count\n",
    "            else:\n",
    "                break\n",
    "            node = node.child[tmp]\n",
    "        return nums\n",
    "\n",
    "class Solution:\n",
    "    def sumPrefixScores(self, words: List[str]) -> List[int]:\n",
    "        #构建前缀树\n",
    "        trie = Trie()\n",
    "        answer = []\n",
    "        for i in range(len(words)):\n",
    "            trie.insert(words[i])\n",
    "            \n",
    "        for i in range(len(words)):\n",
    "            answer.append(trie.getNums(words[i]))\n",
    "        return answer\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Node:\n",
    "    def __init__(self) -> None:\n",
    "        self.val = 1\n",
    "        self.children = [None] * 26\n",
    "\n",
    "class Solution:\n",
    "    def sumPrefixScores(self, words: List[str]) -> List[int]:\n",
    "        root = Node()\n",
    "        for word in words:\n",
    "            node = root\n",
    "            for c in word:\n",
    "                i = ord(c) - ord('a')\n",
    "                if node.children[i] is None:\n",
    "                    node.children[i] = Node()\n",
    "                    node = node.children[i]\n",
    "                else:\n",
    "                    node = node.children[i]\n",
    "                    node.val += 1\n",
    "        ans = [0] * len(words)\n",
    "        for i, word in enumerate(words):\n",
    "            node = root\n",
    "            for c in word:\n",
    "                j = ord(c) - ord('a')\n",
    "                node = node.children[j]\n",
    "                ans[i] += node.val\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Trie:\n",
    "    def __init__(self):\n",
    "        self.children = [None] * 26\n",
    "        self.cnt = 1\n",
    "\n",
    "class Solution:\n",
    "    def sumPrefixScores(self, words: List[str]) -> List[int]:\n",
    "        self.tree = Trie()\n",
    "        for word in words:\n",
    "            cur = self.tree\n",
    "            for ch in word:\n",
    "                if not cur.children[ord(ch) - 97]:\n",
    "                    cur.children[ord(ch) - 97] = Trie()\n",
    "                else:\n",
    "                    cur.children[ord(ch) - 97].cnt += 1\n",
    "                cur = cur.children[ord(ch) - 97]\n",
    "        \n",
    "        ans = []\n",
    "        for word in words:\n",
    "            cur = self.tree\n",
    "            tmp = 0\n",
    "            for ch in word:\n",
    "                tmp += cur.children[ord(ch) - 97].cnt\n",
    "                cur = cur.children[ord(ch) - 97]\n",
    "            ans.append(tmp)\n",
    "        return ans\n",
    "        \n",
    "                    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Node:\n",
    "    def __init__(self) -> None:\n",
    "        self.val = 1\n",
    "        self.children = [None] * 26\n",
    "\n",
    "class Solution:\n",
    "    def sumPrefixScores(self, words: List[str]) -> List[int]:\n",
    "        root = Node()\n",
    "        for word in words:\n",
    "            node = root\n",
    "            for c in word:\n",
    "                i = ord(c) - ord('a')\n",
    "                if node.children[i] is None:\n",
    "                    node.children[i] = Node()\n",
    "                    node = node.children[i]\n",
    "                else:\n",
    "                    node = node.children[i]\n",
    "                    node.val += 1\n",
    "        ans = [0] * len(words)\n",
    "        for i, word in enumerate(words):\n",
    "            node = root\n",
    "            for c in word:\n",
    "                j = ord(c) - ord('a')\n",
    "                node = node.children[j]\n",
    "                ans[i] += node.val\n",
    "        return ans\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Node:\n",
    "    def __init__(self, cnt=0):\n",
    "        self.cnt = cnt\n",
    "        self.nxt = [None] * 26\n",
    "\n",
    "class Solution:\n",
    "    def sumPrefixScores(self, words: List[str]) -> List[int]:\n",
    "        root = Node()\n",
    "        for word in words:\n",
    "            cur = root\n",
    "            for c in word:\n",
    "                if cur.nxt[ord(c) - ord('a')] is None:\n",
    "                    cur.nxt[ord(c) - ord('a')] = Node()\n",
    "                cur = cur.nxt[ord(c) - ord('a')]\n",
    "                cur.cnt += 1\n",
    "        ans = [0] * len(words)\n",
    "        for i, word in enumerate(words):\n",
    "            cur = root\n",
    "            res = 0\n",
    "            for c in word:\n",
    "                cur = cur.nxt[ord(c) - ord('a')]\n",
    "                res += cur.cnt\n",
    "            ans[i] = res\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Trie:\n",
    "    def __init__(self):\n",
    "        self.children = [None] * 26\n",
    "        self.isEnd = False\n",
    "        self.cnt = 0\n",
    "\n",
    "    def searchPrefix(self, prefix: str) -> \"Trie\":\n",
    "        '''\n",
    "        搜索前缀\n",
    "        '''\n",
    "        node = self\n",
    "        for ch in prefix:\n",
    "            idx = ord(ch) - ord(\"a\")\n",
    "            if not node.children[idx]:\n",
    "                return None\n",
    "            node = node.children[idx]\n",
    "        return node\n",
    "\n",
    "    def insert(self, word: str) -> None:\n",
    "        '''\n",
    "        插入一个单词\n",
    "        '''\n",
    "        node = self\n",
    "        for ch in word:\n",
    "            idx = ord(ch) - ord(\"a\")\n",
    "            if not node.children[idx]:\n",
    "                node.children[idx] = Trie()\n",
    "            node = node.children[idx]\n",
    "            node.cnt += 1\n",
    "        node.isEnd = True\n",
    "\n",
    "    def cal(self, word):\n",
    "        res = 0\n",
    "        node = self\n",
    "        for ch in word:\n",
    "            idx = ord(ch) - ord(\"a\")\n",
    "            if not node.children[idx]:\n",
    "                node.children[idx] = Trie()\n",
    "            node = node.children[idx]\n",
    "            res += node.cnt\n",
    "        return res\n",
    "        \n",
    "\n",
    "    def search(self, word: str) -> bool:\n",
    "        '''\n",
    "        搜索 word 是否存在\n",
    "        '''\n",
    "        node = self.searchPrefix(word)\n",
    "        return node is not None and node.isEnd\n",
    "\n",
    "    def startsWith(self, prefix: str) -> bool:\n",
    "        '''\n",
    "        搜索是否存在前缀\n",
    "        '''\n",
    "        return self.searchPrefix(prefix) is not None\n",
    "\n",
    "class Solution:\n",
    "    def sumPrefixScores(self, words: List[str]) -> List[int]:\n",
    "        t = Trie()\n",
    "        for w in words:\n",
    "            t.insert(w)\n",
    "\n",
    "        return [t.cal(w) for w in words]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.root = self.Node()\n",
    "\n",
    "    def sumPrefixScores(self, words):\n",
    "        n = len(words)\n",
    "        ans = [0] * n\n",
    "        for w in words:\n",
    "            self.insert(w)\n",
    "        for i in range(n):\n",
    "            cur = self.root\n",
    "            for c in words[i]:\n",
    "                cur = cur.son[ord(c) - ord('a')]\n",
    "                ans[i] += cur.score\n",
    "        return ans\n",
    "\n",
    "    def insert(self, s):\n",
    "        cur = self.root\n",
    "        for c in s:\n",
    "            j = ord(c) - ord('a')\n",
    "            if cur.son[j] is None:\n",
    "                cur.son[j] = self.Node()\n",
    "            cur.score += 1\n",
    "            cur = cur.son[j]\n",
    "        cur.isEnd = True\n",
    "        cur.score += 1\n",
    "\n",
    "    class Node:\n",
    "        def __init__(self):\n",
    "            self.son = [None] * 26\n",
    "            self.isEnd = False\n",
    "            self.score = 0\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Node:\n",
    "    def __init__(self):\n",
    "        self.cnt = 0\n",
    "        self.next = [None] * 26\n",
    "\n",
    "\n",
    "class Tree:\n",
    "    def __init__(self):\n",
    "        self.head = Node()\n",
    "        self.base = ord('a')\n",
    "    \n",
    "    def add(self, word):\n",
    "        node = self.head\n",
    "        idx = None\n",
    "        for i in range(len(word)):\n",
    "            ch = word[i]\n",
    "            idx = ord(ch) - self.base\n",
    "            if node.next[idx] is None:\n",
    "                node.next[idx] = Node()\n",
    "            node = node.next[idx]\n",
    "            node.cnt += 1\n",
    "    \n",
    "    def get(self, word):\n",
    "        # print('get word', word)\n",
    "        node = self.head\n",
    "        idx = None\n",
    "        cnt = 0\n",
    "        for ch in word:\n",
    "            idx = ord(ch) - self.base\n",
    "            node = node.next[idx]\n",
    "            cnt += node.cnt\n",
    "        #     print(word, ch, cnt, node.cnt)\n",
    "        # print()\n",
    "        # print()\n",
    "        return cnt\n",
    "    \n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def sumPrefixScores(self, words: List[str]) -> List[int]:\n",
    "        if words is None or len(words) == 0:\n",
    "            return 0\n",
    "        \n",
    "        tree = Tree()\n",
    "\n",
    "        for word in words:\n",
    "            tree.add(word)\n",
    "        \n",
    "        res = [None] * len(words)\n",
    "        for i in range(len(words)):\n",
    "            res[i] = tree.get(words[i])\n",
    "        \n",
    "        return res\n",
    "\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Trie:\n",
    "    def __init__(self):\n",
    "        self.son = [None] * 26\n",
    "        self.num = 0\n",
    "    def insert(self, s: str) -> None: # O(l)\n",
    "        for c in s:\n",
    "            x = ord(c) - ord('a')\n",
    "            if not self.son[x]:\n",
    "                self.son[x] = Trie()\n",
    "            self = self.son[x] \n",
    "            self.num += 1\n",
    "    def find(self, s: str):    # O(l)\n",
    "        res = 0\n",
    "        for c in s:\n",
    "            x = ord(c) - ord('a')\n",
    "            self = self.son[x] \n",
    "            res += self.num\n",
    "        return res\n",
    "class Solution:\n",
    "    def sumPrefixScores(self, words: List[str]) -> List[int]:\n",
    "        trie = Trie()\n",
    "        for s in words:\n",
    "            trie.insert(s)\n",
    "        n = len(words)\n",
    "        ans = [0] * n \n",
    "        for i, s in enumerate(words):\n",
    "            ans[i] = trie.find(s)\n",
    "        return ans\n",
    "        \n",
    "\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Trie:\n",
    "    # __slots__ = 'son', 'score', 'ids'\n",
    "\n",
    "    def __init__(self):\n",
    "        self.son = defaultdict(Trie)\n",
    "        self.score = 0\n",
    "        self.ids = []\n",
    "\n",
    "class Solution:\n",
    "    def sumPrefixScores(self, words: List[str]) -> List[int]:\n",
    "        \n",
    "        root = Trie()\n",
    "        for i, x in enumerate(words):\n",
    "            cur = root\n",
    "            for ch in x:\n",
    "                cur = cur.son[ch]\n",
    "                cur.score += 1\n",
    "            cur.ids.append(i)\n",
    "           \n",
    "        n = len(words)\n",
    "        ans = [0] * n\n",
    "\n",
    "        def dfs(node, sm):\n",
    "            if node is None:\n",
    "                return \n",
    "            sm += node.score\n",
    "            for i in node.ids:\n",
    "                ans[i] = sm\n",
    "            for child in node.son.values():\n",
    "                dfs(child, sm)\n",
    "        \n",
    "        dfs(root, 0)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Trie:\n",
    "    def __init__(self):\n",
    "        self.child = [None for _ in range(26)]\n",
    "        self.cnt = 0\n",
    "    \n",
    "    def insert(self, word: str) -> None:\n",
    "        rt = self\n",
    "        for c in word:\n",
    "            ID = ord(c) - ord('a')\n",
    "            if rt.child[ID] == None:\n",
    "                rt.child[ID] = Trie()\n",
    "            rt = rt.child[ID]\n",
    "            rt.cnt += 1\n",
    "        \n",
    "    def qeury(self, prefix: str) -> int:\n",
    "        rt = self\n",
    "        res = 0\n",
    "        for c in prefix:\n",
    "            ID = ord(c)- ord('a')\n",
    "            if rt.child[ID] == None:\n",
    "                break\n",
    "            rt = rt.child[ID]\n",
    "            res += rt.cnt\n",
    "        return res\n",
    "\n",
    "class Solution:\n",
    "    def sumPrefixScores(self, words: List[str]) -> List[int]:\n",
    "        n = len(words)\n",
    "\n",
    "        T = Trie()\n",
    "        for word in words:\n",
    "            T.insert(word)\n",
    "        \n",
    "        res = [0 for _ in range(n)]\n",
    "        for i, word in enumerate(words):\n",
    "            res[i] = T.qeury(word)\n",
    "        return res\n",
    "        \n",
    "\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Node:\n",
    "    def __init__(self):\n",
    "        self.son = defaultdict(Node)\n",
    "        self.ids = []\n",
    "        self.score = 0\n",
    "\n",
    "class Solution:\n",
    "    def sumPrefixScores(self, words: List[str]) -> List[int]:\n",
    "        root = Node()\n",
    "        for i, word in enumerate(words):\n",
    "            cur = root\n",
    "            for c in word:\n",
    "                cur = cur.son[c]\n",
    "                cur.score += 1  # 更新所有前缀的分数\n",
    "            cur.ids.append(i)\n",
    "\n",
    "        ans = [0] * len(words)\n",
    "        def dfs(node: Node, sum: int) -> None:\n",
    "            sum += node.score  # 累加分数，即可得到答案\n",
    "            for i in node.ids:\n",
    "                ans[i] = sum\n",
    "            for child in node.son.values():\n",
    "                if child:\n",
    "                    dfs(child, sum)\n",
    "        dfs(root, 0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Node:\n",
    "    def __init__(self):\n",
    "        self.son = defaultdict(Node) # 表示的是cur下的二十六个字母的字典\n",
    "        self.score = 0\n",
    "        self.ids = []\n",
    "class Solution:\n",
    "    def sumPrefixScores(self, words: List[str]) -> List[int]:\n",
    "        # 核心思想，找出每个word的所有前缀，统计每个前缀的单词个数，然后加在一起\n",
    "        # 字典树（一种存储字符串的数据结构）\n",
    "        # 第一步，存储\n",
    "        root = Node()\n",
    "        for i,word in enumerate(words):\n",
    "            cur = root\n",
    "            for c in word:\n",
    "            # 正常应该是判断有没有cur.son[c]没有的话就创建cur.son[c]\n",
    "                cur = cur.son[c]\n",
    "                cur.score += 1\n",
    "            cur.ids.append(i)\n",
    "        # 第二步，找每个单词的分数\n",
    "        # 类似于遍历二叉树\n",
    "        ans = [0]*len(words)\n",
    "        def dfs(node,sum_):\n",
    "            if node is None:return\n",
    "            sum_ += node.score\n",
    "            for i in node.ids:\n",
    "                ans[i] = sum_\n",
    "            # 遍历它的儿子\n",
    "            for child in node.son.values():\n",
    "                dfs(child,sum_)\n",
    "        dfs(root,0)\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 定义字典树\n",
    "class Node:\n",
    "    def __init__(self):\n",
    "        self.son = defaultdict(Node)\n",
    "        self.score = 0\n",
    "        self.ids = []\n",
    "class Solution:\n",
    "    def sumPrefixScores(self, words: List[str]) -> List[int]:\n",
    "        # 存储每个单词\n",
    "        root = Node()\n",
    "        for i,word in enumerate(words):\n",
    "            cur = root\n",
    "            for c in word:\n",
    "                cur = cur.son[c]\n",
    "                cur.score += 1\n",
    "            cur.ids.append(i)\n",
    "        ans = [1]*(len(words))\n",
    "        def dfs(node,sum_):\n",
    "            if node is None:\n",
    "                return\n",
    "            sum_ += node.score\n",
    "            for i in node.ids:\n",
    "                ans[i] = sum_\n",
    "            for child in node.son.values():\n",
    "                dfs(child,sum_)\n",
    "        dfs(root,0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Node:\n",
    "    def __init__(self):\n",
    "        self.son = defaultdict(Node)\n",
    "        self.ids = []\n",
    "        self.score = 0\n",
    "\n",
    "class Solution:\n",
    "    def sumPrefixScores(self, words: List[str]) -> List[int]:\n",
    "        root = Node()\n",
    "        for i, word in enumerate(words):\n",
    "            cur = root\n",
    "            for c in word:\n",
    "                cur = cur.son[c]\n",
    "                cur.score += 1  # 更新所有前缀的分数\n",
    "            cur.ids.append(i)\n",
    "\n",
    "        ans = [0] * len(words)\n",
    "        def dfs(node: Node, sum: int) -> None:\n",
    "            sum += node.score  # 累加分数，即可得到答案\n",
    "            for i in node.ids:\n",
    "                ans[i] = sum\n",
    "            for child in node.son.values():\n",
    "                if child:\n",
    "                    dfs(child, sum)\n",
    "        dfs(root, 0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Node:\n",
    "    def __init__(self):\n",
    "        self.son = defaultdict(Node)\n",
    "        self.ids = []\n",
    "        self.score = 0\n",
    "\n",
    "class Solution:\n",
    "    def sumPrefixScores(self, words: List[str]) -> List[int]:\n",
    "        root = Node()\n",
    "        for i, word in enumerate(words):\n",
    "            cur = root\n",
    "            for c in word:\n",
    "                cur = cur.son[c]\n",
    "                cur.score += 1  # 更新所有前缀的分数\n",
    "            cur.ids.append(i)\n",
    "\n",
    "        ans = [0] * len(words)\n",
    "        def dfs(node: Node, sum: int) -> None:\n",
    "            sum += node.score  # 累加分数，即可得到答案\n",
    "            for i in node.ids:\n",
    "                ans[i] = sum\n",
    "            for child in node.son.values():\n",
    "                if child:\n",
    "                    dfs(child, sum)\n",
    "        dfs(root, 0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Node:\n",
    "    def __init__(self):\n",
    "        self.son = defaultdict(Node)\n",
    "        self.ids = []\n",
    "        self.score = 0\n",
    "\n",
    "class Solution:\n",
    "    def sumPrefixScores(self, words: List[str]) -> List[int]:\n",
    "        root = Node()\n",
    "        for i, word in enumerate(words):\n",
    "            cur = root\n",
    "            for c in word:\n",
    "                cur = cur.son[c]\n",
    "                cur.score += 1  # 更新所有前缀的分数\n",
    "            cur.ids.append(i)\n",
    "\n",
    "        ans = [0] * len(words)\n",
    "        def dfs(node: Node, sum: int) -> None:\n",
    "            sum += node.score  # 累加分数，即可得到答案\n",
    "            for i in node.ids:\n",
    "                ans[i] = sum\n",
    "            for child in node.son.values():\n",
    "                if child:\n",
    "                    dfs(child, sum)\n",
    "        dfs(root, 0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Node:\n",
    "    def __init__(self):\n",
    "        self.children = defaultdict(Node)\n",
    "        self.score = 0\n",
    "        self.indices = []\n",
    "\n",
    "class Solution:\n",
    "    def sumPrefixScores(self, words: List[str]) -> List[int]:\n",
    "        root = Node()\n",
    "        for i, word in enumerate(words):\n",
    "            node = root\n",
    "            for c in word:\n",
    "                node = node.children[c]\n",
    "                node.score += 1\n",
    "            node.indices.append(i)\n",
    "\n",
    "        ans = [0] * len(words)\n",
    "        def dfs(x, s):\n",
    "            if x is None:\n",
    "                return 0\n",
    "            s += x.score\n",
    "            for i in x.indices:\n",
    "                ans[i] = s\n",
    "            for v in x.children.values():\n",
    "                dfs(v, s)\n",
    "        dfs(root, 0)\n",
    "        return ans\n",
    "                \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumPrefixScores(self, words: List[str]) -> List[int]:\n",
    "        \"\"\"\n",
    "        b  b(2)               2\n",
    "        bc b(2) bc(1)         2 + 1\n",
    "        ab a(2) ab(2)         2 + 2\n",
    "       abc a(2) ab(2) abc(1)  2 + 2 + 1\n",
    "        \"\"\"\n",
    "        n = len(words)\n",
    "        ans = [0] * n\n",
    "        mp = defaultdict(int)\n",
    "        for i, s in enumerate(words):\n",
    "            for j in range(len(s)):\n",
    "                c = s[:j + 1]\n",
    "                mp[c] += 1\n",
    "        for i, s in enumerate(words):\n",
    "            cnt = sum(mp[s[:j + 1]]  for j in range(len(s)))\n",
    "            ans[i] = cnt\n",
    "        return ans\n",
    "\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumPrefixScores(self, words: List[str]) -> List[int]:\n",
    "        res = Counter()\n",
    "        for i in words:\n",
    "            s = \"\"\n",
    "            for j in i:\n",
    "                s += j\n",
    "                res[s] += 1\n",
    "        ans = [0]*len(words)\n",
    "        # print(res)\n",
    "        for i,x in enumerate(words):\n",
    "            s = \"\"\n",
    "            val = 0\n",
    "            for j in x:\n",
    "                s += j\n",
    "                val += res[s]\n",
    "            ans[i] = val\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumPrefixScores(self, words: List[str]) -> List[int]:\n",
    "        cnt = Counter(w[:i+1] for w in words for i in range(len(w)))\n",
    "        return [sum(cnt[w[:i+1]] for i in range(len(w))) for w in words]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def sumPrefixScores(self, words: List[str]) -> List[int]:\r\n",
    "        scores = dict()\r\n",
    "        for w in words:\r\n",
    "            for i in range(1, len(w)+1):\r\n",
    "                prefix = w[0:i]\r\n",
    "                if prefix in scores:\r\n",
    "                    scores[prefix] += 1\r\n",
    "                else:\r\n",
    "                    scores[prefix] = 1\r\n",
    "        res = [0] * len(words)\r\n",
    "        for i, w in enumerate(words):\r\n",
    "            for j in range(1, len(w)+1):\r\n",
    "                res[i] += scores[w[0:j]]\r\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumPrefixScores(self, words: List[str]) -> List[int]:\n",
    "        di={}\n",
    "        total=0\n",
    "        re=[]\n",
    "        for word in words:\n",
    "            for i in range(len(word)):\n",
    "                di[word[0:i+1]]=di.get(word[0:i+1],0)+1\n",
    "        for word in words:\n",
    "            total=0\n",
    "            for i in range(len(word)):\n",
    "                total=total+int(di.get(word[0:i+1],0))\n",
    "            re.append(total)\n",
    "        return re"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumPrefixScores(self, words: List[str]) -> List[int]:\n",
    "        cnt = Counter()\n",
    "        ans = [0] * len(words)\n",
    "        for word in words:\n",
    "            for i in range(1, len(word)+1):\n",
    "                cnt[word[:i]] += 1\n",
    "\n",
    "        for i,word in enumerate(words):\n",
    "            for j in range(1, len(word) + 1):\n",
    "                ans[i] += cnt[word[:j]]\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumPrefixScores(self, words: List[str]) -> List[int]:\n",
    "        dic = {}\n",
    "        for word in words:\n",
    "            for i in range(1, len(word) + 1):\n",
    "                key = word[:i]\n",
    "                if key in dic:\n",
    "                    dic[key] += 1\n",
    "                else:\n",
    "                    dic[key] =1\n",
    "        ans = []\n",
    "        for word in words:\n",
    "            s = 0\n",
    "            for i in range(1, len(word) + 1):\n",
    "                key = word[:i]\n",
    "                s += dic[key]\n",
    "            ans.append(s)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumPrefixScores(self, words: List[str]) -> List[int]:\n",
    "        dic = collections.defaultdict(int)\n",
    "        for word in words:\n",
    "            for i in range(1, len(word) + 1):\n",
    "                key = word[:i]\n",
    "                dic[key] += 1\n",
    "        ans = []\n",
    "        for word in words:\n",
    "            s = 0\n",
    "            for i in range(1, len(word) + 1):\n",
    "                key = word[:i]\n",
    "                s += dic[key]\n",
    "            ans.append(s)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumPrefixScores(self, words: List[str]) -> List[int]:\n",
    "        dic = collections.defaultdict(int)\n",
    "        for word in words:\n",
    "            for i in range(1, len(word) + 1):\n",
    "                key = word[:i]\n",
    "                dic[key] += 1\n",
    "        ans = []\n",
    "        for word in words:\n",
    "            s = 0\n",
    "            for i in range(1, len(word) + 1):\n",
    "                key = word[:i]\n",
    "                s += dic[key]\n",
    "            ans.append(s)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumPrefixScores(self, words: List[str]) -> List[int]:\n",
    "        di={}\n",
    "        res=0\n",
    "        ans=[]\n",
    "        for word in words:\n",
    "            for a in range(len(word)):\n",
    "                di[word[:a+1]]=di.get(word[:a+1],0)+1\n",
    "        for word in words:\n",
    "            res=0\n",
    "            for a in range(len(word)):\n",
    "                res+=int(di.get(word[:a+1],0))\n",
    "            ans.append(res)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumPrefixScores(self, words: List[str]) -> List[int]:\n",
    "        di={}\n",
    "        total=0\n",
    "        re=[]\n",
    "        for word in words:\n",
    "            for i in range(len(word)):\n",
    "                di[word[0:i+1]]=di.get(word[0:i+1],0)+1\n",
    "        for word in words:\n",
    "            total=0\n",
    "            for i in range(len(word)):\n",
    "                total=total+int(di.get(word[0:i+1],0))\n",
    "            re.append(total)\n",
    "        return re"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumPrefixScores(self, words: List[str]) -> List[int]:\n",
    "        dic = collections.defaultdict(int)\n",
    "        for word in words:\n",
    "            for i in range(1, len(word) + 1):\n",
    "                key = word[:i]\n",
    "                if key in dic:\n",
    "                    dic[key] += 1\n",
    "                else:\n",
    "                    dic[key] = 1\n",
    "        ans = []\n",
    "        for word in words:\n",
    "            s = 0\n",
    "            for i in range(1, len(word) + 1):\n",
    "                key = word[:i]\n",
    "                s += dic[key]\n",
    "            ans.append(s)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumPrefixScores(self, words: List[str]) -> List[int]:\n",
    "        di={}\n",
    "        total=0\n",
    "        re=[]\n",
    "        for word in words:\n",
    "            for i in range(len(word)):\n",
    "                di[word[0:i+1]]=di.get(word[0:i+1],0)+1\n",
    "        for word in words:\n",
    "            total=0\n",
    "            for i in range(len(word)):\n",
    "                total=total+int(di.get(word[0:i+1],0))\n",
    "            re.append(total)\n",
    "        return re"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumPrefixScores(self, words: List[str]) -> List[int]:\n",
    "        dic = collections.defaultdict(int)\n",
    "        for word in words:\n",
    "            for i in range(1, len(word) + 1):\n",
    "                key = word[:i]\n",
    "                dic[key] += 1\n",
    "        ans = []\n",
    "        for word in words:\n",
    "            s = 0\n",
    "            for i in range(1, len(word) + 1):\n",
    "                key = word[:i]\n",
    "                s += dic[key]\n",
    "            ans.append(s)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumPrefixScores(self, words: List[str]) -> List[int]:\n",
    "\n",
    "        cnt=Counter()\n",
    "        for w in words:\n",
    "            for i,v in enumerate(w):\n",
    "                cnt[w[:i+1]]+=1\n",
    "\n",
    "        res=[]\n",
    "        for w in words:\n",
    "            ans=0\n",
    "            for i,v in enumerate(w):\n",
    "                ans+=cnt[w[:i+1]]\n",
    "            res.append(ans)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumPrefixScores(self, words: List[str]) -> List[int]:\n",
    "\n",
    "        cnt=Counter()\n",
    "        for w in words:\n",
    "            for i,v in enumerate(w):\n",
    "                cnt[w[:i+1]]+=1\n",
    "\n",
    "        res=[]\n",
    "        for w in words:\n",
    "            ans=0\n",
    "            for i,v in enumerate(w):\n",
    "                if w[:i+1] in cnt:\n",
    "                    ans+=cnt[w[:i+1]]\n",
    "                else:\n",
    "                    break\n",
    "            res.append(ans)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumPrefixScores(self, words: List[str]) -> List[int]:\n",
    "        # 核心思想，找出每个word的所有前缀，统计每个前缀的单词个数，然后加在一起\n",
    "        # 简单想法首先有个\n",
    "        # 统计cnt\n",
    "        # 时间复杂度 O(n*m)\n",
    "        cnt = Counter()\n",
    "        for word in words:\n",
    "            m = len(word)\n",
    "            for j in range(m):\n",
    "                cur = word[:j+1]\n",
    "                cnt[cur] += 1\n",
    "        # 时间复杂度 O(n*m)\n",
    "        n = len(words)\n",
    "        ans = [0]*n\n",
    "        for i,word in enumerate(words):\n",
    "            # 枚举word的每一个前缀\n",
    "            m = len(word)\n",
    "            for j in range(m):\n",
    "                cur = word[:j+1]\n",
    "                ans[i] += cnt[cur]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumPrefixScores(self, words: List[str]) -> List[int]:\n",
    "        dict_head = collections.defaultdict(int)\n",
    "        ans = []\n",
    "        for word in words:\n",
    "            for i in range(len(word)):\n",
    "                dict_head[word[0:i + 1]] += 1\n",
    "        for word in words:\n",
    "            s = 0\n",
    "            for i in range(len(word)):\n",
    "                s += dict_head[word[0:i + 1]]\n",
    "            ans.append(s)\n",
    "        return ans\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumPrefixScores(self, words: List[str]) -> List[int]:\n",
    "        di={}\n",
    "        total=0\n",
    "        re=[]\n",
    "        for word in words:\n",
    "            for i in range(len(word)):\n",
    "                di[word[0:i+1]]=di.get(word[0:i+1],0)+1\n",
    "        for word in words:\n",
    "            total=0\n",
    "            for i in range(len(word)):\n",
    "                total=total+int(di.get(word[0:i+1],0))\n",
    "            re.append(total)\n",
    "        return re"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumPrefixScores(self, words: List[str]) -> List[int]:\n",
    "        n = len(words)\n",
    "        d = collections.defaultdict(int)\n",
    "        for i in range(n):\n",
    "            w = words[i]\n",
    "            m = len(w)\n",
    "            for j in range(1, m + 1):\n",
    "                d[w[:j]] += 1\n",
    "        # print(d)\n",
    "        ans = list()\n",
    "        for i in range(n):\n",
    "            w = words[i]\n",
    "            m = len(w)\n",
    "            cnt = 0\n",
    "            for j in range(1, m + 1):\n",
    "                cnt += d[w[:j]]\n",
    "            ans.append(cnt)\n",
    "            \n",
    "        return ans \n",
    "                \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumPrefixScores(self, words: List[str]) -> List[int]:\n",
    "        cnt = Counter(w[:i+1] for w in words for i in range(len(w)))\n",
    "        return [sum(cnt[w[:i+1]] for i in range(len(w))) for w in words]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumPrefixScores(self, words: List[str]) -> List[int]:\n",
    "        cnt = Counter(w[:i+1] for w in words for i in range(len(w)))\n",
    "        return [sum(cnt[w[:i+1]] for i in range(len(w))) for w in words]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumPrefixScores(self, words: List[str]) -> List[int]:\n",
    "        # hashmap来统计\n",
    "        hashmap = {}\n",
    "        count = [[]]*len(words)\n",
    "        for i in range(len(words)):\n",
    "            word = words[i]\n",
    "            qian = ''\n",
    "            for w in word:\n",
    "                qian += w \n",
    "                if qian in hashmap:\n",
    "                    hashmap[qian] += 1\n",
    "                else:\n",
    "                    hashmap[qian] = 1\n",
    "        res = [0]*len(words)\n",
    "        for i in range(len(words)):\n",
    "            word = words[i]\n",
    "            qian = ''\n",
    "            count = 0\n",
    "            for w in word:\n",
    "                qian += w \n",
    "                count += hashmap[qian]\n",
    "            res[i] = count\n",
    "        return res"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
